# 4 寻找两个正序数组的中位数
# leetcode第4题: https://leetcode.cn/problems/median-of-two-sorted-arrays/
# Date: 2024/10/21


def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    total_length = len(nums1) + len(nums2)
    odd = total_length % 2  # 奇数个元素返回单一数值, 偶数个元素返回两数平均数
    k = (total_length - 1) // 2
    if len(nums1) == 0:
        return nums2[k]
    if len(nums2) == 0:
        return nums1[k]
    while k != 0:
        index = k - 1
        if nums1[index] >= nums2[index]:
            nums2 = nums2[k:]
        else:
            nums1 = nums1[k:]
        k //= 2

    if odd:
        return nums1[0] if nums1[0] < nums2[0] else nums2[0]
    else:
        return (nums1[0] + nums2[0]) / 2


def findMedianSortedArrays_opt(nums1: list, nums2: list) -> float:
    def get_k_min(nums1: list, start1: int, end1: int, nums2: list, start2: int, end2: int, k: int):
        """使用折半删除的方法, 获得两个数组中的第k小的数字"""
        remain1 = end1 - start1 + 1  # 表示折半删除后的剩余数组的长度
        remain2 = end2 - start2 + 1
        if remain1 == 0:
            return nums2[start2 + k - 1]
        if remain2 == 0:
            return nums1[start1 + k - 1]
        if k == 1:
            return min(nums1[start1], nums2[start2])
        i = start1 + min(remain1, k // 2) - 1  # 两个数组的指针
        j = start2 + min(remain2, k // 2) - 1
        if nums1[i] <= nums2[j]:
            return get_k_min(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1))
        else:
            return get_k_min(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1))

    m, n = len(nums1), len(nums2)
    mid1 = (m + n + 1) // 2
    mid2 = (m + n + 2) // 2
    a = get_k_min(nums1, 0, m - 1, nums2, 0, n - 1, mid1)
    b = get_k_min(nums1, 0, m - 1, nums2, 0, n - 1, mid2)
    return (a + b) / 2


if __name__ == '__main__':
    # nums1, nums2 = [], [1]
    # print(findMedianSortedArrays(nums1, nums2))
    # nums1, nums2 = [1, 3], [2]
    # print(findMedianSortedArrays(nums1, nums2))
    # nums1, nums2 = [1, 2], [3, 4]
    # print(findMedianSortedArrays(nums1, nums2))
    # nums1, nums2 = [0, 0, 0, 0, 0], [-1, 0, 0, 0, 0, 0, 1]
    nums1, nums2 = [1, 4, 5, 7, 8], [2, 3, 6, 9]
    print(findMedianSortedArrays_opt(nums1, nums2))
